package 数据结构练习;

public class 快速排序 {
    public static void main(String[] args) {
        int a[] = new int[]{5,9,6,7,3,1,2,4,8};
        sort(a,0,a.length-1);
        for(int x:a){
            System.out.print(x+" ");
        }
    }

    public static void sort(int[] a,int l,int r){
        //判断递归越界
        if(l == r || l<0 || l>r || r>=a.length){
            return;
        }
        int top = l,tail = r;
        int center = a[top];
        int c;
        l++;
        while (true){
            //移动右指针
            while (a[r]>center && l!=r){
                r--;
            }
            //移动左指针
            while (a[l]<center && l!=r){
                l++;
            }
            //交换
            if(l != r){
                c = a[l];
                a[l] = a[r];
                a[r] = c;
            }
            //如果左右指针重合
            else {
                c = a[top];
                a[top] = a[r];
                a[r] = c;
                break;
            }
        }
        //递归下一层
        sort(a,top,l-1);
        sort(a,r+1,tail);
    }

}
